package sort;

import java.util.Arrays;

public class MergeSort {
    public static void mergeSort(int[] array) {
        mergeSortRange(array,0,array.length);
    }
    public static void merge(int[] array,int from,int mid,int to) {
        int size = to - from;
        int[] tmp = new int[size];
        int left = from;
        int right = mid;
        int dest = 0;
        while(left < mid && right < to) {  //循环结束必定有一区间没有遍历
            if(array[left] <= array[right]) {
                tmp[dest++] = array[left++];
            }else{
                tmp[dest++] = array[right++];
            }
        }

        while(left < mid) {
            tmp[dest++] = array[left++];
        }
        while(right < to) {
            tmp[dest++] = array[right++];
        }
        //dest下标从0开始,array的下标从from开始
        for(int i = 0;i < size;i++) {
            array[from + i] = tmp[i];  //偏移量都是相同的
        }
        //将tmp中的元素复制会原来的array数组中
        //if (size >= 0) System.arraycopy(tmp, 0, array, from, size);
    }
    public static void mergeSortRange(int[] array,int from,int to) {
        int size = to - from;
        if(size <= 1){
            return;
        }
        int mid = from + size / 2;
        //先处理[from,mid)区间, 再处理[mid,to)区间
        mergeSortRange(array,from,mid);
        mergeSortRange(array,mid,to);
        //合并两个有序区间
        merge(array,from,mid,to);
    }

    public static void main(String[] args) {
//        int[] array = {1,3,4,2,1,8,10,6};
//        int[] array = {1,2,3,4,5,6,7,8};
        int[] array = {7,6,5,4,3,2,1};

        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }
}
